package sort

import (
	"math"
	"sort"
)

type BucketSort struct {
	BaseSort
}

// Sort 排序时放到临时数组里面了
func (self BucketSort) Sort() {

	bucketSize := 5
	if self.Array == nil || self.Len() < 2 {
		return
	}
	max, min := self.getMost()

	distance := max - min //大小为 min 的偏移值
	////创建 d / 5 + 1 个桶，第 i 桶存放  5*i ~ 5*i+5-1范围的数
	bucketNum := int(math.Floor(float64(distance)/float64(bucketSize))) + 1

	buckets := make([][]int, bucketNum)
	for _, e := range self.Array {
		index := int(math.Floor(float64(e-min) / float64(bucketSize)))
		buckets[index] = append(buckets[index], e)
	}


	arrIndex := 0
	for _, bucket := range buckets {
		if len(bucket) <= 0 {
			continue
		}
		//对数据进行排序
		sort.Ints(bucket)

		for _, e := range bucket {
			self.Array[arrIndex] = e
			arrIndex++
		}
	}
}

func (self BucketSort) getMost() (max int, min int) {

	for _, e := range self.Array {
		if e > max {
			max = e
		}
		if min > e {
			min = e
		}
	}
	return max, min
}
func (self BucketSort) Name() string {
	return "桶排序"
}
